package com.example.demo.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 链接:<a href="https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150">https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150</a> <br>
 * <p>
 * <p>
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。<br>
 * <p>
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。<br>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [100,4,200,1,3,2] <br>
 * 输出：4 <br>
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。<br>
 * 示例 2：<br>
 * <p>
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1] <br>
 * 输出：9 <br>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 10^5<br>
 * -10^9 <= nums[i] <= 10^9
 *
 * <p>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/01/24 11:32
 */
public class _128_最长的连续序列 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 0, 1};
        int i = new Solution().longestConsecutive(nums);
        System.out.println(i);
    }

    public static class Solution {

        /**
         * 方法一：排序
         * 时间复杂度为O(nlogn + n)
         * 空间复杂度为O(1)
         *
         * @param nums
         * @return
         */
        public int longestConsecutive(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            Arrays.sort(nums);
            int maxLength = 1;
            int length = 1;
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i + 1] - nums[i] == 1) {
                    length++;
                } else if (nums[i + 1] - nums[i] == 0) {
                    continue;
                } else {
                    length = 1;
                }
                maxLength = Math.max(maxLength, length);
            }
            return maxLength;
        }


        /**
         * 官方解说：哈希表
         * <p>
         * 我们考虑枚举数组中的每个数 x，考虑以其为起点，不断尝试匹配 x+1,x+2,⋯x+1, x+2,⋯ 是否存在，<br>
         * 假设最长匹配到了 x+y，那么以 x 为起点的最长连续序列即为 x,x+1,x+2,⋯,x+y，其长度为 y+1，我们不断枚举并更新答案即可。<br>
         * 对于匹配的过程，暴力的方法是 O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1) 的时间复杂度。<br>
         * <p>
         * <p>
         * 仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 O(n^2)（即外层需要枚举 O(n) 个数，内层需要暴力匹配 O(n) 次），无法满足题目的要求。<br>
         * 但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个 x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，
         * 那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。<br>
         * <p>
         * <p>
         * 那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，
         * 不然按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
         * <p>
         * <p>
         * 时间复杂度：O(n)，其中 n 为数组的长度。具体分析已在上面正文中给出。
         * <p>
         * 空间复杂度：O(n)。哈希表存储数组中所有的数需要 O(n) 的空间。
         */
        public int longestConsecutive1(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }
            int maxLength = 0;
            for (int num : set) {
                if (!set.contains(num - 1)) {
                    int length = 1;
                    while (set.contains(num + 1)) {
                        length++;
                        num++;
                    }
                    maxLength = Math.max(maxLength, length);
                }
            }
            return maxLength;
        }
    }
}
